package 力扣._239滑动窗口最大值;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] r = new int[nums.length + 1 - k];
        //优先队列
        PriorityQueue<Integer> queue = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            r[i - k] = queue.peek();
            //删除指定值的元素，复杂度应该是O(n),这样就把整体拖慢了，成为n^2了
            queue.remove(nums[i-k]);    //这一步可以优化，可以将下标、值一起放到优先队列中，最大值不再窗口内就继续出堆
            queue.add(nums[i]);
        }
        r[r.length-1] = queue.peek();
        return r;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,3,-1,-3,5,3,6,7};
        int k=3;
        int[] ints = new Solution().maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(Arrays.stream(ints).toArray()));
    }
}
